# coding: utf-8
'''
Created on 23/06/2013

@author: Vagner Clementino
'''

def egcd(a, b):
    '''
        Algoritmo de Euclides Estendido. 
        Retorna b = mdc (a, b) e os interios x, y
        que satisfazem a equação:
        ax + by = d

    '''
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q,r = b//a,b%a;
        m,n = x-u*q,y-v*q #  x//y significa floor "floor division"
        b,a, x,y, u,v = a,r, u,v, m,n
    mdc = b
    return mdc, x, y

def inverse_mod_n(a,n):
    '''
        Retorna o inverso a mod n, caso ele exista
        Caso inverso não resista o método retorna 'None'
    '''
    g, x, y = egcd(a, n) 
    if g != 1:
        print ("Impossível encontrar o inverso de {} mod  {}".format(a,n))
        return None
    else:
        return x % n

'''
def inverse_mod_n(a,n):
    inverse = (-1) * a
    inverse = inverse % n
    return inverse
'''